package leetcode2;
import java.util.*;
public class Day5 {

    //01背包【模版】
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            //1.输入信息
            int n = in.nextInt();
            int v = in.nextInt();
            int[][] nums = new int[n+1][2]; //表示物品 0：体积    1：价值
            for(int i=1;i<=n;i++) {
                nums[i][0] = in.nextInt();
                nums[i][1] = in.nextInt();
            }
            int[][] dp = new int[n+1][v+1];
            //2.第一问
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=v;j++) {
                    //1.不选i物品
                    int a = dp[i-1][j]; //价值
                    //2.选i物品 j - i物品体积
                    int b=0;
                    if(j - nums[i][0] >=0 ) {
                        b = nums[i][1] + dp[i-1][j-nums[i][0]];
                    }
                    dp[i][j]=Math.max(a,b);
                }
            }
            System.out.println(dp[n][v]);
            //3.第二问
            for(int i=1;i<=v;i++) dp[0][i]=-1;
            //dp[i][j]:1-i物品，刚好装满j的价值
            for(int i=1;i<=n;i++) {
                for(int j=1;j<=v;j++) {
                    //1.不选i物品
                    int a = dp[i-1][j]; //价值
                    //2.选i物品 j - i物品体积
                    int b=-1;
                    if(j - nums[i][0] >= 0 && dp[i-1][j-nums[i][0]]!=-1) {//剩余体积>0 && 体积加起来
                        b = nums[i][1] + dp[i-1][j-nums[i][0]];
                    }
                    dp[i][j]=Math.max(a,b);
                }
            }
            System.out.println(dp[n][v]<0?0:dp[n][v]);
        }
    }

}
